package 哈希表;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/7 16:52
 */
public class Note {

    /*
     - lc 560 这是 一道 非常关键的板子题， 如果把这个题给整明白的话， 很多题，都可以 变形到这道题的思想上面，来做！
     - lc 525 就是这样的 做的， 只不过， 相当于求 子数组和 为 0 的 最长子数组
     - 魔法师这道题， 也可以这样来解题！


     */

    /*

      理解 一下  哈希 结构的 一个 特性 (有点)
      以及  有时候  可以使用  数组 来 实现 map (哈希 表)
     */







    /*
     使用 原地 哈希 对一个  长度 为 n  数组 arr 并 且 arr[i] ∈ [1,n] or ∈ [0, n - 1]
     (不能有 重复元素)
     进行  (升序 ) 排序
     时间复杂度 o(N)
     */

    /*
     arr[i] ∈ [1 , n]
     */
    @Test
    public void test(){
        int nums [] = {5,4,3,2,1};
        /*
         下面 这样写, 一定会
         */
        for(int i = 0;i < nums.length;i++){
            while(nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]){
                swap(nums,i,nums[i] - 1);
            }
        }
        System.out.println(Arrays.toString(nums));
    }

    private void swap(int nums[],int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }



    /*
     将上面的 原地 hash 的 思想， 与  index 数组 进行 一个类比的思考
     */


    @Test
    public void test1(){
        int n = 10;
        /*
         原数组
    nums[i] :    3  4  5  1  2  0
        i:       0  1  2  3  4  5
         */
        int nums[] = new int[n];

        // 索引 Index 数组
        Integer []index = new Integer[n];

        /*
         对应 index 数组 按照 nums 中值 从小到大 进行一个排序！
         而
      index[i] :  i
      i    :      nums[i] (值排好序的 一个 序列)
      而 这个 对应关系 就是 上面的  nums[i] 和 i 对应关系的  ,倒着的情况
      即: 在 index 数组 中,  index[i] 表示的是 nums 数组中  第 i 小的 下标(升序 排序下)
      eg: index[0] 表示 的 是  数组 nums 中  minest 的 值得下标, 剩下 的以此类推!
         */
        Arrays.sort(index,(a, b) -> nums[a] - nums[b]);



    }








}
